#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>

#define MAX_V 3     // 最大顶点数 (V0,V1,V2)
#define INF INT_MAX // 表示无穷大

// 创建图结构
typedef struct
{
    char name[3]; // 顶点名称
} Vertex;

typedef struct
{
    Vertex vertices[MAX_V];
    int vCount;
    int adjMatrix[MAX_V][MAX_V]; // 邻接矩阵
} Graph;

// 1. 创建图
Graph *createGraph()
{
    Graph *g = (Graph *)malloc(sizeof(Graph));
    g->vCount = 0;
    // 初始化邻接矩阵
    for (int i = 0; i < MAX_V; i++)
    {
        for (int j = 0; j < MAX_V; j++)
        {
            if (i == j)
                g->adjMatrix[i][j] = 0; // 对角线为0
            else
                g->adjMatrix[i][j] = INF;
        }
    }
    return g;
}

// 2. 添加顶点
void addVertex(Graph *g, const char *name)
{
    if (g->vCount >= MAX_V)
    {
        printf("Error: Graph is full\n");
        return;
    }
    strcpy(g->vertices[g->vCount].name, name);
    g->vCount++;
}

// 3. 添加边
void addEdge(Graph *g, int v1, int v2, int weight)
{
    if (v1 < 0 || v1 >= g->vCount || v2 < 0 || v2 >= g->vCount)
    {
        printf("Error: Invalid vertex index\n");
        return;
    }
    g->adjMatrix[v1][v2] = weight;
}

// 4. Floyd算法实现
void Floyd(Graph *g)
{
    int A[MAX_V][MAX_V];    // 路径长度矩阵
    int Path[MAX_V][MAX_V]; // 前驱结点矩阵
    // 初始化A和Path矩阵
    for (int i = 0; i < g->vCount; i++)
    {
        for (int j = 0; j < g->vCount; j++)
        {
            A[i][j] = g->adjMatrix[i][j];
            if (i != j && g->adjMatrix[i][j] < INF)
            {
                Path[i][j] = i; // i到j有直接路径
            }
            else
            {
                Path[i][j] = -1; // 无直接路径
            }
        }
    }
    // Floyd算法核心
    for (int k = 0; k < g->vCount; k++)
    {
        for (int i = 0; i < g->vCount; i++)
        {
            for (int j = 0; j < g->vCount; j++)
            {
                if (A[i][k] != INF && A[k][j] != INF &&
                    A[i][k] + A[k][j] < A[i][j])
                {
                    A[i][j] = A[i][k] + A[k][j];
                    Path[i][j] = Path[k][j];
                }
            }
        }
    }
    // 打印A矩阵
    printf("\nA matrix:\n\t");
    for (int i = 0; i < g->vCount; i++)
    {
        printf("%s\t", g->vertices[i].name);
    }
    printf("\n");
    for (int i = 0; i < g->vCount; i++)
    {
        printf("%s\t", g->vertices[i].name);
        for (int j = 0; j < g->vCount; j++)
        {
            if (A[i][j] == INF)
                printf("INF\t");
            else
                printf("%d\t", A[i][j]);
        }
        printf("\n");
    }
    // 打印Path矩阵
    printf("\nPath matrix:\n\t");
    for (int i = 0; i < g->vCount; i++)
    {
        printf("%s\t", g->vertices[i].name);
    }
    printf("\n");
    for (int i = 0; i < g->vCount; i++)
    {
        printf("%s\t", g->vertices[i].name);
        for (int j = 0; j < g->vCount; j++)
        {
            if (Path[i][j] == -1)
                printf("NULL\t");
            else
                printf("%s\t", g->vertices[Path[i][j]].name);
        }
        printf("\n");
    }
}

// 5. 销毁图
void destroyGraph(Graph *g)
{
    free(g);
}

int main()
{
    // 创建图
    Graph *g = createGraph();

    // 添加顶点
    addVertex(g, "V0");
    addVertex(g, "V1");
    addVertex(g, "V2");

    // 添加边
    addEdge(g, 0, 1, 6);  // V0->6->V1
    addEdge(g, 1, 0, 10); // V1->10->V0
    addEdge(g, 0, 2, 13); // V0->13->V2
    addEdge(g, 2, 0, 5);  // V2->5->V0
    addEdge(g, 1, 2, 4);  // V1->4->V2

    // 执行Floyd算法
    Floyd(g);

    // 销毁图
    destroyGraph(g);
    return 0;
}